//给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。 
//
// update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。 
//
// 示例: 
//
// Given nums = [1, 3, 5]
//
//sumRange(0, 2) -> 9
//update(1, 2)
//sumRange(0, 2) -> 8
// 
//
// 说明: 
//
// 
// 数组仅可以在 update 函数下进行修改。 
// 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。 
// 
// Related Topics 树状数组 线段树 
// 👍 209 👎 0

package com.leetcode.editor.cn;

//Java：区域和检索 - 数组可修改
class P307RangeSumQueryMutable {
    public static void main(String[] args) {
        NumArray solution = new P307RangeSumQueryMutable().new NumArray(new int[]{1, 3, 5});
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class NumArray {
        int[] tree;
        int n;

        public NumArray(int[] nums) {
            if (nums.length > 0) {
                n = nums.length;
                tree = new int[n * 2];
                buildTree(nums);
            }
        }

        private void buildTree(int[] nums) {
            for (int i = n, j = 0; i < 2 * n; i++, j++) {
                tree[i] = nums[j];
            }
            for (int i = n - 1; i > 0; --i) {
                tree[i] = tree[i * 2] + tree[i * 2 + 1];
            }
        }

        public void update(int i, int val) {
            i += n;
            tree[i] = val;
            while (i > 0) {
                int left = i;
                int right = i;
                if (i % 2 == 0) {
                    right = i + 1;
                } else {
                    left = i - 1;
                }
                // parent is updated after child is updated
                tree[i / 2] = tree[left] + tree[right];
                i /= 2;
            }
        }

        public int sumRange(int i, int j) {
            i += n;
            j += n;
            int sum = 0;
            while (i <= j) {
                if ((i % 2) == 1) {
                    sum += tree[i];
                    i++;
                }
                if ((j % 2) == 0) {
                    sum += tree[j];
                    j--;
                }
                i /= 2;
                j /= 2;
            }
            return sum;
        }
    }


/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */
//leetcode submit region end(Prohibit modification and deletion)

}